package com.lw.leetcode.dp.b;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 2054. 两个最好的不重叠活动
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/6 17:25
 */
public class MaxTwoEvents {

    public static void main(String[] args) {
        MaxTwoEvents test = new MaxTwoEvents();

        // 4
//        int[][] arr = {{1,3,2},{4,5,2},{2,4,3}};

        // 5
//        int[][] arr = {{1,3,2},{4,5,2},{1,5,5}};

        // 8
        int[][] arr = {{1, 5, 3}, {1, 5, 1}, {6, 6, 5}};

        int i = test.maxTwoEvents(arr);
        System.out.println(i);

    }

    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1]));
        int length = events.length;
        int[] as = new int[length];
        int[] bs = new int[length];
        TreeMap<Integer, Integer> amap = new TreeMap<>();
        as[0] = events[0][2];
        bs[0] = events[0][2];
        amap.put(events[0][1], as[0]);
        for (int i = 1; i < length; i++) {
            int[] event = events[i];
            as[i] = Math.max(as[i - 1], event[2]);
            amap.put(event[1], as[i]);
            Integer key = amap.floorKey(event[0] - 1);
            int count = 0;
            if (key != null) {
                count = amap.get(key);
            }
            bs[i] = Math.max(bs[i - 1], count + event[2]);
        }
        return bs[length - 1];
    }

}
